package bishi.alibaba.BISAI;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @Info:
 * @Author: Tangxz
 * @Date: 2020/09/18 10:38
 */
public class one {
    public static void main(String[] args) {
        System.out.println(shortestSubarray(new int[]{1,2,1},7));
    }
    public static int shortestSubarray(int[] A, int K) {
        Deque<Integer> deque = new LinkedList<>();
        if(A.length==0){
            return 0;
        }
        if(Arrays.stream(A).max().getAsInt()>=K){
            return 1;
        }
        long sum = 0;
        int daan = Integer.MAX_VALUE;
        for(int i=0;i<A.length;i++){
            sum+=A[i];
            deque.offerLast(A[i]);
            while(sum>=K){
                daan = daan<deque.size()?daan:deque.size();
                sum = sum - deque.pollFirst();
            }
        }
        return daan==Integer.MAX_VALUE?0:daan;
    }
    public int shortestSubarray2(int[] A, int K) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();

        int minLength = Integer.MAX_VALUE;

        int[] sum = new int[A.length + 1];
        //先获取 前缀和
        for (int i = 1; i <= A.length; ++i) {
            sum[i] = sum[i - 1] + A[i - 1];
        }

        for (int i = 0; i < sum.length; ++i) {
            if (i != 0) {
                while (dq.size() > 0 && sum[dq.peekLast()] >= sum[i]) {
                    dq.pollLast();
                }

                while (dq.size() > 0 && sum[i] - sum[dq.peekFirst()] >= K) {
                    minLength = Math.min(minLength, i - dq.pollFirst());
                }
            }
            dq.addLast(i);
        }
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}
